package com.datastructure2.graph;

import com.sun.jmx.remote.internal.ArrayQueue;
import org.junit.Test;
import sun.misc.Queue;

import java.sql.Array;
import java.util.*;

/**
 * @author: 临晖
 * @date: 2024/03/22
 * @description:
 */
public class Solution {

    /**
     * 797. 所有可能的路径
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
     * <p>
     * graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
     *
     * @param graph
     * @return
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        path.add(0);
        allPathSourceTarget_(graph, 0, path, res);

        return res;

    }

    public void allPathSourceTarget_(int[][] graph, int startIndex, List<Integer> path, List<List<Integer>> res) {
        //if (path.size() == graph.length - 1) {
        //    res.add(new ArrayList<>(path));
        //    return;
        //}

        //if (graph[startIndex].length == 0 || path.size() == graph.length - 1) {
        //    res.add(new ArrayList<>(path));
        //        return;
        //}

        if (path.get(path.size() - 1) == graph.length - 1) {
            res.add(new ArrayList<>(path));
            return;
        }


        for (int i = 0; i < graph[startIndex].length; i++) {
            path.add(graph[startIndex][i]);

            allPathSourceTarget_(graph, graph[startIndex][i], path, res);

            path.remove(path.size() - 1);
        }
    }


    //public int numIslands(char[][] grid) {
    //    int m = grid.length;
    //    int n = grid[0].length;
    //
    //    boolean[][] isVisited = new boolean[m][n];
    //    int res = 0;
    //    for (int i = 0; i < m; i++) {
    //        for (int j = 0; j < n; j++) {
    //            if (grid[i][j] == '1' && !isVisited[i][j]) {
    //                res++;
    //                numIslandsDFS(grid, isVisited, i, j);
    //            }
    //        }
    //    }
    //
    //    return res;
    //}

    //public void numIslandsDFS(char[][] grid, boolean[][] isVisited, int x, int y) {
    //    isVisited[x][y] = true;
    //
    //    for (int i = 0;i < dir.length; i++) {
    //        int nextX = x + dir[i][0];
    //        int nextY = y + dir[i][1];
    //
    //        if ((nextX < 0 || nextX >= grid.length) || (nextY < 0 || nextY >= grid[0].length)) {
    //            continue;
    //        }
    //
    //        if (!isVisited[nextX][nextY] && grid[nextX][nextY] == '1') {
    //            numIslandsDFS(grid, isVisited, nextX, nextY);
    //        }
    //    }
    //}
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        boolean[][] isVisited = new boolean[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !isVisited[i][j]) {
                    res++;
                    numIslandsBFS(grid, isVisited, i, j);
                }
            }
        }

        return res;
    }

    public void numIslandsBFS(char[][] grid, boolean[][] isVisited, int x, int y) {
        LinkedList<int[]> qu = new LinkedList<>();
        qu.addLast(new int[]{x, y});
        isVisited[x][y] = true;

        while (!qu.isEmpty()) {
            int[] curr = qu.getFirst();
            for (int i = 0; i < dir.length; i++) {
                int nextX = curr[0] + dir[i][0];
                int nextY = curr[1] + dir[i][1];

                if ((nextX < 0 || nextX >= grid.length) || (nextY < 0 || nextY >= grid[0].length)) {
                    continue;
                }

                if (!isVisited[nextX][nextY] && grid[nextX][nextY] == '1') {
                    qu.addLast(new int[]{nextX, nextY});
                    isVisited[nextX][nextY] = true;
                }
            }

            qu.removeFirst();
        }

    }


    //int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        boolean[][] isVisited = new boolean[m][n];
        int res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !isVisited[i][j]) {
                    res = Math.max(res, maxAreaOfIslandDFS(grid, isVisited, i, j));
                }
            }

        }

        return res;
    }

    public int maxAreaOfIslandDFS(int[][] grid, boolean[][] isVisited, int x, int y) {
        isVisited[x][y] = true;

        int sum = 0;

        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if ((nextX < 0 || nextX >= grid.length) || (nextY < 0 || nextY >= grid[0].length)) {
                continue;
            }

            if (!isVisited[nextX][nextY] && grid[nextX][nextY] == 1) {
                sum += maxAreaOfIslandDFS(grid, isVisited, nextX, nextY);
            }
        }

        return sum + 1;

    }


    /**
     * 1020. 飞地的数量
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
     * <p>
     * 一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
     * <p>
     * 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
     *
     * @param grid
     * @return
     */
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < grid.length; i++) {
            if (grid[i][0] == 1) {
                numEnclaves(grid, i, 0);
            }
            if (grid[i][grid[0].length - 1] == 1) {
                numEnclaves(grid, i, grid[0].length - 1);
            }
        }
        //初始化的時候，j 的上下限有調整過，必免重複操作。
        for (int j = 1; j < grid[0].length - 1; j++) {
            if (grid[0][j] == 1) {
                numEnclaves(grid, 0, j);
            }
            if (grid[grid.length - 1][j] == 1) {
                numEnclaves(grid, grid.length - 1, j);
            }
        }

        int res = 0;


        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1) {
                    res += numEnclaves(grid, i, j);
                }
            }

        }

        return res;
    }

    public int numEnclaves(int[][] grid, int x, int y) {
        grid[x][y] = 0;     //当前节点置为0

        int sum = 0;

        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if ((nextX < 0 || nextX >= grid.length) || (nextY < 0 || nextY >= grid[0].length)) {
                continue;
            }

            if (grid[nextX][nextY] == 1) {
                sum += numEnclaves(grid, nextX, nextY);
            }
        }

        return sum + 1;

    }


    /**
     * 130. 被围绕的区域
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     *
     * @param board
     */
    //int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;

        char oldOp = 'O';
        char newOp = 'A';
        //初始化，将边上的'O'变为'A'
        for (int i = 0; i < m; i++) {
            if (board[i][0] == oldOp) {
                solveDfs(board, i, 0, oldOp, newOp);
            }
            if (board[i][n - 1] == oldOp) {
                solveDfs(board, i, n - 1, oldOp, newOp);
            }
        }


        for (int j = 1; j < n - 1; j++) {
            if (board[0][j] == oldOp) {
                solveDfs(board, 0, j, oldOp, newOp);
            }
            if (board[m - 1][j] == oldOp) {
                solveDfs(board, m - 1, j, oldOp, newOp);
            }
        }

        oldOp = 'O';
        newOp = 'X';
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == oldOp) {
                    solveDfs(board, i, j, oldOp, newOp);
                }
            }
        }


        oldOp = 'A';
        newOp = 'O';
        for (int i = 0; i < m; i++) {
            if (board[i][0] == oldOp) {
                solveDfs(board, i, 0, oldOp, newOp);
            }
            if (board[i][n - 1] == oldOp) {
                solveDfs(board, i, n - 1, oldOp, newOp);
            }
        }


        for (int j = 1; j < n - 1; j++) {
            if (board[0][j] == oldOp) {
                solveDfs(board, 0, j, oldOp, newOp);
            }
            if (board[m - 1][j] == oldOp) {
                solveDfs(board, m - 1, j, oldOp, newOp);
            }
        }


    }


    public void solveDfs(char[][] board, int x, int y, char oldOp, char newOp) {
        board[x][y] = newOp;

        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if (nextX < 0 || nextX >= board.length || nextY < 0 || nextY >= board[0].length) {
                continue;
            }

            if (board[nextX][nextY] == oldOp) {
                solveDfs(board, nextX, nextY, oldOp, newOp);
            }
        }
    }


    /**
     *
     * 827. 最大人工岛
     * 困难
     * 相关标签
     * 相关企业
     * 给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
     * 返回执行此操作后，grid 中最大的岛屿面积是多少？
     * 岛屿 由一组上、下、左、右四个方向相连的 1 形成。
     *
     * @param grid
     * @return
     */
    int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public int largestIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int res = 0;
        boolean falg = true;
        boolean[][] isVisited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {        //是海洋
                    grid[i][j] = 1;     //将当前编程陆地
                    res = Math.max(res, largestIslandDFS(grid, isVisited, i, j));
                    grid[i][j] = 0;     //变回海洋
                    for (int z = 0; z < isVisited.length; z++) {
                        Arrays.fill(isVisited[z], false);
                    }
                    falg = false;

                }
            }
        }

        if (falg) {
            return m * n;
        }

        return res;
    }

    private int largestIslandDFS(int[][] grid, boolean[][] isVisited, int x, int y) {
        isVisited[x][y] = true;
        int sum = 0;
        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }

            if (grid[nextX][nextY] == 1 && !isVisited[nextX][nextY]) {
                sum += largestIslandDFS(grid, isVisited, nextX, nextY);
            }

        }
        return sum + 1;
    }



    //public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    //    HashSet<String> wordSet = new HashSet<>(wordList); //转换为hashset 加快速度
    //    if (wordSet.size() == 0 || !wordSet.contains(endWord)) {  //特殊情况判断
    //        return 0;
    //    }
    //    Queue<String> queue = new LinkedList<>(); //bfs 队列
    //    queue.offer(beginWord);
    //    Map<String, Integer> map = new HashMap<>(); //记录单词对应路径长度
    //    map.put(beginWord, 1);
    //
    //    while (!queue.isEmpty()) {
    //        String word = queue.poll(); //取出队头单词
    //        int path  = map.get(word); //获取到该单词的路径长度
    //        for (int i = 0; i < word.length(); i++) { //遍历单词的每个字符
    //            char[] chars = word.toCharArray(); //将单词转换为char array，方便替换
    //            for (char k = 'a'; k <= 'z'; k++) { //从'a' 到 'z' 遍历替换
    //                chars[i] = k; //替换第i个字符
    //                String newWord = String.valueOf(chars); //得到新的字符串
    //                if (newWord.equals(endWord)) {  //如果新的字符串值与endWord一致，返回当前长度+1
    //                    return path + 1;
    //                }
    //                if (wordSet.contains(newWord) && !map.containsKey(newWord)) { //如果新单词在set中，但是没有访问过
    //                    map.put(newWord, path + 1); //记录单词对应的路径长度
    //                    queue.offer(newWord);//加入队尾
    //                }
    //            }
    //        }
    //    }
    //    return 0; //未找到
    //}
    //


    @Test
    public void myTest() {
        char[][] grid = {
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'X', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'X'}
        };

        solve(grid);
    }


}
